/*-
 * Copyright (c) 2006, 2007 FTS Team
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 4. Neither the name of the FTS Team nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *      QueryParser.hpp
 *
 * $FTS$
 */
#ifndef _QUERY_PARSER_HPP__
#define _QUERY_PARSER_HPP__ 1

/**
  @file QueryParser.hpp
  @brief Search query parser class
*/

// C includes
  #include <stdio.h>

// Local Includes
#include <CharIterator.hpp>
#include <FTS.hpp>
#include <HashFunctions.hpp>
#include <LemmatizerInterface.hpp>
#include <STLVector.hpp>

namespace FTSS // FullTextSearchSystem
{
// FWD
class InvIndexStorage;
class StopWords;
/*

Expr = Base { Operator Base }

Operator = "" | "&" | "|" | "^" | "!" | "!!"

Base = Word | Number | "(" Expr ")"

Number = digit{digit}

Word = Digit | Letter { Digit | Letter }

Letter = "A-Za-z0x80-0xFF".

Digit  = "0123456789".

Ignore = ' ' | '\t' | '\r' | '\n'

*/

#define C_END_OF_STREAM                         1
#define C_SUCCESS                               0
#define C_SYNTAX_ERROR                         -6
#define C_NEXT_PARADIGM_ERROR                  -7
#define C_DEFAULT_OPERATOR                     -8

#define C_EXACT_MATCH                           0x00000001
#define C_FIRST_CAPITAL                         0x00000002
#define C_ALL_CAPITAL                           0x00000004
#define C_CYRILLIC                              0x00000008
#define C_LATIN                                 0x00000010
#define C_MIXED_LANGUAGE                        (C_LATIN | C_CYRILLIC)
#define C_NUMBER                                0x00000020
#define C_STOPWORD                              0x00000040
#define C_NOT                                   0x00000080

#define C_MAX_TOKENS 512

/**
  @enum eQueryTokenType QueryParser.hpp <QueryParser.hpp>
  @brief Type of token
*/
enum eQueryTokenType
{
	/** OR  operator             */
	Q_OR,
	/** AND operator             */
	Q_AND,
	/** NOT operator             */
	Q_NOT,
	/** Right Bracket            */
	Q_RIGHT_BRACKET,
	/** Left Bracket             */
	Q_LEFT_BRACKET,
	/** Data (word, number, etc) */
	Q_WORD,
	/** End of query             */
	Q_END
};

/**
  @struct QueryToken QueryParser.hpp <QueryParser.hpp>
  @brief Generic query token
*/
struct QueryToken
{
	/** Type of token                      */
	eQueryTokenType               token_type;
	/** Parent token                       */
	QueryToken                  * parent;
	/** Number of documents, contains word */
	INT_32                        doc_count;
	/** Inverted document frequency        */
	W_FLOAT                       idf;
	/** Weight of quorum                   */
	W_FLOAT                       quorum_weight;
	/** List of matched documents          */
	STLW::vector<DocumentEntry *> doc_entries;
	/** Current position in list
	         of matched documents          */
	UINT_32                       doc_entries_pos;
	/** Current WordEntry offset           */
	UINT_32                       doc_entry_pos;
	/** Current WordEntry token position   */
	UINT_32                       doc_entry_we_pos;

	/** Various flags                      */
	UINT_32                       flags;

	/** Constructor                        */
	inline QueryToken(eQueryTokenType oTokenType = Q_END): token_type(oTokenType),
	                                                       parent(NULL),
	                                                       doc_count(0),
	                                                       idf(0.0),
	                                                       quorum_weight(0.0),
	                                                       doc_entries_pos(0),
	                                                       doc_entry_pos(0),
	                                                       doc_entry_we_pos(0),
	                                                       flags(0) { ;; }
	/** A destructor              */
	virtual ~QueryToken() throw() { ;; }
};

/**
  @struct QueryWord QueryParser.hpp <QueryParser.hpp>
  @brief Query word.
*/
struct QueryWord:
  public QueryToken
{
	/** Word hash                  */
	TokenHash_t        word_hash;
	/** Form of word               */
	TokenHash_t        word_form;
	/** Type of word               */
	INT_32             word_type;
	/** Word position              */
	UINT_16            query_pos;
	/** Token Data                 */
	UCCHAR_P           begin_token;
	/** Data Length                */
	UCCHAR_P           end_token;
	/** Current document entry     */
	DocumentEntry    * current_doc_entry;
	/** Position in document entry */
	UINT_32            current_doc_entry_pos;

	/**
	  @brief Constructor
	  @param iWordForm - word form
	  @param iWordType - type of word
	  @param iQueryPos - position in query
	  @param sBeginToken - start of token
	  @param sEndToken - end of token
	*/
	inline QueryWord(const TokenHash_t & iWordForm   = 0,
	                 const INT_32      & iWordType   = 0,
	                 const INT_16      & iQueryPos   = 0,
	                 UCCHAR_P            sBeginToken = NULL,
	                 UCCHAR_P            sEndToken   = NULL): QueryToken(Q_WORD),
	                                                          word_form(iWordForm),
	                                                          word_type(iWordType),
	                                                          query_pos(iQueryPos),
	                                                          begin_token(sBeginToken),
	                                                          end_token(sEndToken),
	                                                          current_doc_entry(NULL),
	                                                          current_doc_entry_pos(0)
	{
		word_hash = HashFunc((CCHAR_8 *)sBeginToken, (sEndToken - sBeginToken));
	}

	/** A destructor              */
	inline ~QueryWord() throw() { ;; }

};

/**
  @struct QueryTokenList QueryParser.hpp <QueryParser.hpp>
  @brief List of query tokens, emulation for multinode tree
*/
struct QueryTokenList
{
	/** Pointer to token              */
	QueryToken     * token;
	/** Pointer to next token or NULL */
	QueryTokenList * next;
	/** Default constructor */
	inline QueryTokenList(): token(NULL), next(NULL) { ;; }
};

/**
  @struct QueryOperator QueryParser.hpp <QueryParser.hpp>
  @brief Query operator (AND, OR, NOT)
*/
struct QueryOperator:
  public QueryToken
{
	/** Children subtree list     */
	QueryTokenList     * children;
	/** Children count            */
	UINT_32              child_count;

	/**
	  @brief Constructor
	  @param oTokenType - type of token
	*/
	inline QueryOperator(eQueryTokenType oTokenType = Q_END): QueryToken(oTokenType), children(NULL), child_count(0) { ;; }

	/** A destructor              */
	~QueryOperator() throw() { ;; }
};

/**
  @class LevelCounter QueryParser.hpp <QueryParser.hpp>
  @brief Recursion level counter
*/
class LevelCounter
{
	/** Recursion Level */
	INT_32    & iLevel;
	/** Method name     */
	CCHAR_P     szMethod;
public:
	/**
	  @brief Constructor
	  @param iILevel - Recursion Level
	  @param szIMethod - method name
	  @param sCode - Code
	*/
	inline LevelCounter(INT_32 & iILevel, CCHAR_P szIMethod, UCCHAR_P sCode): iLevel(iILevel)
	{
		iLevel++;
#ifdef _DEBUG
		szMethod = szIMethod;
		for (INT_32 iC = 0; iC < iLevel; iC++) { fprintf(stderr, "    |"); }
		fprintf(stderr, "-> %s: '%s'\n", szMethod, sCode);
#endif
	}

	/**
	  @brief A destructor
	*/
	~LevelCounter() throw()
	{
#ifdef _DEBUG
		for (INT_32 iC = 0; iC < iLevel; iC++) { fprintf(stderr, "    |"); }
		fprintf(stderr, "<- %s\n", szMethod);
#endif
		iLevel--;
	}
};

/**
  @class QueryParser QueryParser.hpp <QueryParser.hpp>
  @brief Query parser
*/
class QueryParser
{
public:
	/**
	  @brief Constructor
	  @param oILemmatizer - lemmatizer object
	  @param sQuery - query
	  @param iQueryLen - query size
	  @param iUseMorph - use morphology or not
	  @param eDefaultOp - default operator
	*/
	QueryParser(LemmatizerInterface & oILemmatizer, UCCHAR_P sQuery, UINT_32 iQueryLen, INT_32 iUseMorph = 1, eQueryTokenType eDefaultOp = Q_AND);

	/**
	  @brief Get parsed query
	  @return parsed query
	*/
	QueryToken * GetParsed();

	/**
	  @brief Get number of words
	  @return Number of parsed words
	*/
	INT_32       GetWordsNum();

	/**
	  @brief Get number of words
	  @return Number of parsed words
	*/
	INT_32       GetMaxWordPos();

	/**
	  @brief Get list of all words
	  @return List of all words
	*/
	QueryWord  * GetAllWords();

	/**
	  @brief A destructor
	*/
	~QueryParser() throw();
private:

	/** Maximum length of the word                   */
        static const UINT_32 C_WORD_MAX_LEN = 1024;
        /** Length of the buffer                         */
        static const UINT_32 C_WORD_BUFFER_LEN = C_WORD_MAX_LEN * 6;
        /** Buffer for operations with words             */
        static CHAR_8 sWordBuffer[C_WORD_BUFFER_LEN];


	/** Normal iterator         */
	typedef CharIterator<UCHAR_8>  NormalIterator;
	/** Constant iterator       */
	typedef CharIterator<UCCHAR_8> ConstIterator;

	/** Parsed tokens           */
	QueryTokenList aParsedTokens[C_MAX_TOKENS + 1];
	/** Parsed query, operators */
	QueryOperator  aParsedOperators[C_MAX_TOKENS + 1];
	/** Parsed query, words     */
	QueryWord      aParsedWords[C_MAX_TOKENS + 1];

	/** Lemmatizer              */
	LemmatizerInterface  & oLemmatizer;
	/** Token position          */
	INT_32            iTokenPos;
	/** Operator position       */
	INT_32            iOperatorPos;
	/** Word position           */
	INT_32            iWordPos;
	/** Words count             */
	INT_32            iRealPos;
	/** Bracket recursion level */
	INT_32            iInBracket;
	/** Recursion Level         */
	INT_32            iLevel;
	/** Use morphology or not   */
	INT_32            iUseMorph;
	/** Default operator        */
	eQueryTokenType   eDefaultOp;
	/** Root token              */
	QueryToken      * pRoot;

	/**
	  @brief Next subtree entry
	  @param pCurrentSubtreeEntry - current entry
	  @param pToken - current token
	  @param pCurrentOperator - current operator
	  @return list of query tokens
	*/
	inline QueryTokenList * NextSubtreeEntry(QueryTokenList * pCurrentSubtreeEntry, QueryToken * pToken, QueryOperator * pCurrentOperator)
	{
		QueryTokenList * pTMP = &aParsedTokens[iTokenPos];
		pTMP -> token = pToken;
		if (pCurrentSubtreeEntry != NULL) { pCurrentSubtreeEntry -> next = pTMP; }
		else                              { pCurrentOperator -> children = pTMP; }
		++iTokenPos;
		return pTMP;
	}

	/**
	  @brief Expr = MathExpr [Comparison MathExpr]
	  @param iS - current stream position
	  @param iSEnd - end of stream position
	  @param pTMPRoot - current token
	  @return Error code
	*/
	INT_32 IsExpr        (ConstIterator & iS, ConstIterator iSEnd, QueryToken ** pTMPRoot);

	/**
	  @brief Base = Function | Variable | Number | String12 | "(" MathExpr ")"
	  @param iS - current stream position
	  @param iSEnd - end of stream position
	  @param pTMPRoot - current token
	  @return Error code
	*/
	INT_32 IsBase        (ConstIterator & iS, ConstIterator iSEnd, QueryToken ** pTMPRoot);

	// //////////////////////////////////////////////////////////////////////////////////////////////////
	//
	// Simple cases
	//

	/**
	  @brief Operator "" | "&" | "|" | "^" | "!"
	  @param iS - current stream position
	  @param iSEnd - end of stream position
	  @param oToken - type of token
	  @return Error code
	*/
	INT_32 IsOperator    (ConstIterator & iS, ConstIterator iSEnd, eQueryTokenType & oToken);

	/**
	  @brief Word = Letter | digit { Letter | digit }
	  @param iS - current stream position
	  @param iSEnd - end of stream position
	  @param pTMPRoot - current token
	  @return Error code
	*/
	INT_32 IsWord        (ConstIterator & iS, ConstIterator iSEnd, QueryToken ** pTMPRoot);

	/**
	  @brief Ignore = ' ' | TAB | CR | LF
	  @param iS - current stream position
	  @param iSEnd - end of stream position
	*/
	INT_32 IgnorableChars(ConstIterator & iS, ConstIterator iSEnd);
};

/**
  @class QueryPreprocessor QueryParser.hpp <QueryParser.hpp>
  @brief Aprioristic estimation weights of query quorums
*/
class QueryPreprocessor
{
public:
	/**
	  @brief Constructor
	  @param dIStopWordWeight - weight of stopword
	  @param dISoftness - softness parameter
	  @param pIStorage - data storage
	  @param oIStopWords - stop words database
	*/
	QueryPreprocessor(W_FLOAT dIStopWordWeight, W_FLOAT dISoftness, InvIndexStorage * pIStorage, StopWords & oIStopWords);

	/**
	  @brief Estimate weights of query quorums
	  @param pRootNode - root node of syntactic tree
	  @return processed tree
	*/
	QueryToken * ProcessQuery(QueryToken * pRootNode);

private:
	/**
	  @brief Recursive estimation weights of query quorums
	  @param pToken - current token
	  @param iLevel - recursion level
	*/
	void DescendTree(QueryToken * pToken, INT_32 & iLevel);

	/** IDF weight for stop words         */
	W_FLOAT            dStopWordWeight;
	/** Softness coefficient for quorums  */
	W_FLOAT            dSoftness;
	/** Data storage                      */
	InvIndexStorage  * pStorage;
	/** Stop words database               */
	StopWords        & oStopWords;
	/** Recursion level                   */
	INT_32             iLevel;
	/** Number of documents in collection */
	INT_32 iDocNum;

};

} // namespace FTSS
#endif // _QUERY_PARSER_HPP__
// End.
